解題程式碼

var pathSum = function (root, targetSum) {
  if (!root) return [];
  const res = [];

  const DFS = (node, path, curSum) => {
    if (!node.left && !node.right && curSum === targetSum) {
      res.push(path);
      return;
    }

    if (node.left) DFS(node.left, [...path, node.left.val], curSum + node.left.val);
    if (node.right) DFS(node.right, [...path, node.right.val], curSum + node.right.val);
  };
  DFS(root, [root.val], root.val);

  return res;
};

解題思路、演算法

這題使用 DFS 解題。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)，n 為 tree height

參考資料